Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

\[ \newcommand{\IR}{\mathbb{R}} \newcommand{\IRnn}{\IR_{\geq 0}} \newcommand{\coloneqq}{:=} \newcommand{\eqqcolon}{=:} \newcommand{\sMid}{\,|\,} \newcommand{\SMid}{\middle|} \newcommand{\transp}{^\top} \]

§2 Computation of Mixed Nash Equilibria

Throughout this chapter: Only finite 2-player games $G=([2],S,u)$

Notation: $S_1 = M \coloneqq \set{1,\dots,m}$,   $S_2 = N = \set{m+1,\dots,m+n}$,   $A,B \in \IR^{M\times N}$ utility matrices of player 1/2

§2.1 Full Support Enumeration

Obs. 1.8: $x^* \in \Delta$ is MNE $\iff x^* \in B(x^*) \coloneqq \prod_i B_i(x^*_{-i})$ where $B_i(x^*_{-i}) \coloneqq \set{x_i \in \Delta(S_i) \sMid x_i \text{ best resp. to } x^*_{-i}}$

Thm. 2.2 (Best-Response-Condition (BRC)): $(x,y) \in \Delta$ mixed strategy profile. Then:
  • $x$ best response to $y$ $\iff \bigl(\forall i \in M: x_i \gt 0 \implies \max\set{(Ay)_k \sMid k \in M} \class{tempstep a}{\data{tempstep-from=11}{\eqqcolon u}}\bigr)$
  • $y$ best response to $x$ $\iff \bigl(\forall j \in N: y_j \gt 0 \implies \max\set{(y\transp B)_\ell \sMid \ell \in N} \class{tempstep a}{\data{tempstep-from=11}{\eqqcolon v}}\bigr)$
Alg. 2.1: Full Support Enumeration
Input: Finite 2-player game $G=(N,S,u)$
Output: A mixed NE of $G$
  1. For each $I \subseteq M, J \subseteq N$ Do
  2. mmSolve the system of linear inequalities: \begin{align*} \sum_{i \in I} x_i B_{ij} = v \quad \forall j \in J \qquad & \text{and} \qquad \sum_{i \in I} x_i = 1 \\ \sum_{j \in J} A_{ij} y_j = u \quad \forall i \in I \qquad & \text{and} \qquad \sum_{j \in J} y_j = 1 \\ \sum_{i \in I} x_i B_{ij} \leq v \quad \forall j \in N \setminus J \qquad &\text{and} \qquad x_i \geq 0 \quad \forall i \in I \\ \sum_{j \in J} A_{ij} y_j \leq u \quad \forall i \in M \setminus I \qquad & \text{and} \qquad y_j \geq 0 \quad \forall j \in J \end{align*}
  3. mmIf $\exists$ solution $(x,y)$ Then
  4. mmmmReturn $(x,y)$ (extended with zeros)
Example 2.3: Determine all MNE in the following game:
$4$$5$
$1$$(3\class{clickedVisC}{^*},3\class{clickedVisR}{^*})$$(3\phantom{^*},2\phantom{^*})$
$2$$(2\phantom{^*},2\phantom{^*})$$(5\phantom{^*},6\class{clickedVisR}{^*})$
$3$$(0\phantom{^*},3\class{clickedVisR}{^*})$$(6\class{clickedVisC}{^*},1\phantom{^*})$
Computational Game Theory (WiSe25/26), §2. Computation of Mixed Nash Equilibria
Lukas Graf (lukas.graf@uni-passau.de)
↑ All Slides